package com.xzz.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: hhz
 * @create: 2022-01-12 16:49
 * 435. 无重叠区间
 * 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
 *
 * 注意:
 *
 * 可以认为区间的终点总是大于它的起点。
 * 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
 *
 **/
public class EraseOverlapIntervals {
    public static void main(String[] args) {
        System.out.println(eraseOverlapIntervals(new int[][]{{1,2},{2,3},{3,4},{1,3}}));

        System.out.println(eraseOverlapIntervals(new int[][]{{1,2},{1,2},{1,2}}));

    }
    public static int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));

        int count = 1;
        int end = intervals[0][1];
        for (int[] interval : intervals) {
            int start = interval[0];
            if(start>=end){
                count++;
                end = interval[1];
            }
        }
        return intervals.length-count;
    }
}
